
//2642.设计可以求最短路径的图类
class Graph {
    int _n;
    vector<vector<pair<int,int>>> path ;                   //记录每一条路径
    void _addEdge(vector<int>& edge) {                     //设置一个统一的添加函数,让后面的函数进行复用
        int pos = edge[0] ,next = edge[1] ,t = edge[2];
        path[pos].emplace_back(next,t);
    }
public:
    Graph(int n, vector<vector<int>>& edges) {
        path = vector<vector<pair<int,int>>>(n);           //对path进行初始化
        _n = n;         
        for(auto& nums: edges)                                                
            _addEdge(nums);
    }
    
    void addEdge(vector<int> _edge) {
        _addEdge(_edge);
    }
    
    int shortestPath(int node1, int node2) {
        //使用Dijkstra算法来解决
        //因为是稀疏图所以采用优先级队列来实现
        vector<int> dis(_n,INT_MAX);
        vector<int> vist(_n);
        priority_queue<pair<int,int>,vector<pair<int,int>>,greater<pair<int,int>>> pq;
        pq.push({0,node1});
        vist[node1] = 1;

        while(pq.size())
        {
            auto [clock ,pos] = pq.top();
            pq.pop();
            if(clock >= dis[pos]) continue;
            dis[pos] = clock;
            vist[pos] = 1;
            for(auto& [next,t] : path[pos])
                if(clock + t < dis[next] && !vist[next]) pq.push({clock + t,next});
        }
        return dis[node2] ==INT_MAX? -1 : dis[node2];
    }
};

/**
 * Your Graph object will be instantiated and called as such:
 * Graph* obj = new Graph(n, edges);
 * obj->addEdge(edge);
 * int param_2 = obj->shortestPath(node1,node2);
 */